class Solution
{
public:
    int minimumDistance(vector<vector<int>> &points)
    {
        int n = points.size();

        auto maxManhattan = [&](int exclude)
        {
            int maxSumIdx = -1;
            int maxDiffIdx = -1;
            int minSumIdx = -1;
            int minDiffIdx = -1;

            for (int i = 0; i < n; i++)
            {
                if (i == exclude)
                    continue;
                int sum = points[i][0] + points[i][1];
                int diff = points[i][0] - points[i][1];
                if (maxSumIdx == -1 || sum > points[maxSumIdx][0] + points[maxSumIdx][1])
                {
                    maxSumIdx = i;
                }
                if (maxDiffIdx == -1 || diff > points[maxDiffIdx][0] - points[maxDiffIdx][1])
                {
                    maxDiffIdx = i;
                }
                if (minSumIdx == -1 || sum < points[minSumIdx][0] + points[minSumIdx][1])
                {
                    minSumIdx = i;
                }
                if (minDiffIdx == -1 || diff < points[minDiffIdx][0] - points[minDiffIdx][1])
                {
                    minDiffIdx = i;
                }
            }

            int maxSum = points[maxSumIdx][0] + points[maxSumIdx][1];
            int maxDiff = points[maxDiffIdx][0] - points[maxDiffIdx][1];
            int minSum = points[minSumIdx][0] + points[minSumIdx][1];
            int minDiff = points[minDiffIdx][0] - points[minDiffIdx][1];

            if (maxSum - minSum > maxDiff - minDiff)
            {
                return tuple{maxSum - minSum, maxSumIdx, minSumIdx};
            }
            else
            {
                return tuple{maxDiff - minDiff, maxDiffIdx, minDiffIdx};
            }
        };

        auto [_, i, j] = maxManhattan(-1);
        auto [d1, i1, j1] = maxManhattan(i);
        auto [d2, i2, j2] = maxManhattan(j);
        return min(d1, d2);
    }
};